import java.util.Arrays;
class Zcsh {
    public int minDistance(int[] houses, int k) {
        // https://blog.csdn.net/qq_43539599/article/details/106747425
        Arrays.sort(houses);
        int n = houses.length;
        int[][] dp = new int[n][n]; // dp[i][j]: 第 i 个 房子到 第 j 个房子;一个邮箱的最短距离
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                for (int x = i , y = j; x < y; x++ ,y--) {
                    dp[i][j] += houses[y] - houses[x]; // 该区间内所有房子的距离到中位数房子的距离之和;
                }
            }
        }

        int[][] f = new int[n][k + 1]; // f[i][j]: 前 i 个房子, j 个邮箱最端距离
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < k + 1; j++) 
                f[i][j] = Integer.MAX_VALUE;

        for (int i = 0 ; i < n; i++) f[i][1] = dp[0][i]; 
        
        for (int i = 1; i < n; i++) {
            for (int j = 2; j <= k && j <= i+1; j++) {  //j是个数，但i是下标
                for (int x = j-1; x <= i; x++) {  
                    f[i][j] = Math.min(f[i][j], f[x-1][j-1] + dp[x][i]); 
                }
            }
        }

        return f[n-1][k];
    }
}